// Copyright (c) 2020-present, INSPUR Co, Ltd. All rights reserved.
// This source code is licensed under Apache 2.0 License.
//
// Created by florian on 05.08.15.

#include "tree_node.h"
#include <algorithm>
#include <assert.h>

namespace syn_art_fullkey {

bool N4::insert(uint8_t key, N *n) {
  if (count_ >= 4)
    return false;
  keys_[count_].store(key, std::memory_order_release);
  children_[count_].store(n, std::memory_order_release);
  count_++;
  return true;
}

void N4::change(uint8_t key, N *val) {
  for (uint32_t i = 0; i < count_; ++i) {
    N *child = children_[i].load();
    if (child != nullptr && keys_[i].load() == key) {
      return children_[i].store(val, std::memory_order_release);
    }
  }
  assert(false);
  __builtin_unreachable();
}

N *N4::getChild(const uint8_t k) const {
  for (uint32_t i = 0; i < 4; ++i) {
    N *child = children_[i].load();
    if (child != nullptr && keys_[i].load() == k) {
      return child;
    }
  }
  return nullptr;
}

void N4::getChildrenSmall(uint8_t start, uint8_t end,
                          std::tuple<uint8_t, N *> *&childrenList,
                          uint32_t &childrenCount, u_int32_t childMax) const {
  childrenCount = 0;
  uint32_t i = 0, j = 0;
  for (i = 0; i < count_; ++i) {
    uint8_t key = this->keys_[i].load();
    if (key >= start && key <= end) {
      N *child = this->children_[i].load();
      if (child != nullptr) {
        for (j = 0; j < childrenCount; ++j) {
          if (std::get<0>(childrenList[j]) > key)
            break;
        }
        if (j >= childMax)
          continue;

        int needMoveNum = childrenCount - j;
        for(int m = 0; m < needMoveNum; m++){
          if (childrenCount == childMax) continue;
          childrenList[childrenCount - m] = childrenList[childrenCount - m - 1];
        }
      
        childrenList[j] = std::make_tuple(key, child);
        if (childrenCount < childMax)
          childrenCount++;
      }
    }
  }
}
void N4::getChildrenLarge(uint8_t start, uint8_t end,
                          std::tuple<uint8_t, N *> *&childrenList,
                          uint32_t &childrenCount, u_int32_t childMax) const {
  childrenCount = 0;
  uint32_t i = 0, j = 0;
  for (i = 0; i < count_; ++i) {
    uint8_t key = this->keys_[i].load();
    if (key >= start && key <= end) {
      N *child = this->children_[i].load();
      if (child != nullptr) {
        for (j = 0; j < childrenCount; ++j) {
          if (std::get<0>(childrenList[j]) > key)
            break;
        }
        if (childrenCount == childMax) {
          if (j == 0)
            continue;
          for(uint32_t m = 0; m < j - 1; m++){
            childrenList[m] = childrenList[m + 1];
          }
          childrenList[j - 1] = std::make_tuple(key, child);
        } else {
          int needMoveNum = childrenCount - j;
          for(int m = 0; m < needMoveNum; m++){
           if (childrenCount == childMax) continue;
            childrenList[childrenCount - m] = childrenList[childrenCount - m - 1];
          }
          
          childrenList[j] = std::make_tuple(key, child);
          if (childrenCount < childMax)
            childrenCount++;
        }
      }
    }
  }
}

} // namespace syn_art_fullkey